#include <iostream>
#include <vector>
#include <climits>
#include <string>

using namespace std;

// 分割回文串 II
class Solution
{
public:
    int minCut(string s)
    {
        // 1、在 isPal 表中统计所有字串的回文信息
        int n = s.size();
        vector<vector<bool>> isPal(n, vector<bool>(n));
        for(int i = n - 1; i >= 0; --i)
            for(int j = i; j < n; ++j)
                if(s[i] == s[j])
                    isPal[i][j] = !(i + 1 < j) || isPal[i + 1][j - 1];

        // 2、创建并填写 dp 表
        vector<int> dp(n, INT_MAX);
        for(int i = 0; i < n; ++i)
        {
            if(isPal[0][i])
            {
                dp[i] = 0;
            }
            else
            {
                for(int j = 1; j <= i; ++j)
                {
                    if(isPal[j][i]) dp[i] = min(dp[i], dp[j-1] + 1);
                }
            }
        }
        // 3、返回值
        return dp[n - 1];
    }
};
/*
- 时间复杂度：O(n^2)
- 空间复杂度：O(n^2)
*/

// 最长回文字串
//class Solution
//{
//public:
//    string longestPalindrome(string s)
//    {
//        // 1、建表
//        size_t n = s.size();
//        pair<size_t, size_t> pr(n - 1, 1);
//        vector<vector<bool>> dp(n, vector<bool>(n));
//        // 2、填表
//        for(int i = n - 1; i >= 0; --i)
//        {
//            for(int j = i; j < n; ++j)
//            {
//                if(s[i] == s[j])
//                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
//                if(dp[i][j] && j - i + 1 > pr.second)
//                    pr.first = i, pr.second = j - i + 1;
//            }
//        }
//        // 3、返回值
//        return s.substr(pr.first, pr.second);
//    }
//};



// class Solution
// {
// public:
//     string longestPalindrome(string s)
//     {
//         // 1、建表
//         size_t n = s.size();
//         pair<pair<int, int>, size_t> pr(make_pair(n - 1, n - 1), 1);
//         vector<vector<bool>> dp(n, vector<bool>(n));
//         // 2、填表
//         for(int i = n - 1; i >= 0; --i)
//         {
//             for(int j = i; j < n; ++j)
//             {
//                 if(s[i] == s[j])
//                     dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
//                 if(dp[i][j] && j - i + 1 > pr.second)
//                     pr.first = make_pair(i, j), pr.second = j - i + 1;
//             }
//         }
//         // 3、返回值
//         return s.substr(pr.first.first, pr.second);
//     }
// };

// 分割回文串 IV
//class Solution
//{
//public:
//    bool checkPartitioning(string s)
//    {
//        // 1、用 dp 把所有字串是否是回文预处理一下
//        int n = s.size();
//        vector<vector<bool>> dp(n, vector<bool>(n));
//
//        for(int i = n - 1; i >= 0; --i)
//            for(int j = i; j < n; ++j)
//                if(s[i] == s[j])
//                    i + 1 < j ? dp[i][j] = dp[i + 1][j - 1] : true;
//
//        // 2、枚举所有第二个字符串的起始位置和结束位置
//        for(int i = 1; i < n - 1; ++i)
//            for(int j = i; j < n - 1; ++j)
//                if(dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1])
//                    return true;
//                else
//                    return false;
//    }
//};